本篇同步發布於Blog: [解題] POJ - 2431 Expedition

平台：

PKU Online Judge

題號：

2431 - Expedition

題目連結：

http://poj.org/problem?id=2431

題目說明：

　　有一輛車子要開往城鎮，距離為L單位，且車上目前有P單位的燃料。路上會有N(1 <= N <= 10000)間的加油站，每間加油站距離城鎮x單位、並能補充p單位的燃料。車子每行駛1單位的距離就得消耗1單位的燃料，而車子的燃料容量無限大，求車子抵達城鎮時的最少加油次數，如果達不到則輸出-1。

　　範例輸入是4間加油站，需要在第1家(15 10)和第2家(11 5)加油站加油，才能抵達成鎮。

範例輸入：

4
4 4
5 2
11 5
15 10
25 10

範例輸出：

2

解題方法：

　　這題需轉換問題，可以看成是當車子開到某站時，如果行經距離超過燃料箱的油量，則檢查經過的加油站的備用油，先從最大量的油倒進燃料箱，直到超過消耗量或者仍無法滿足消耗量。

        最大量的油的儲存方式是使用Priority Queue。

　　以範例輸入來看：

1. 目前距離25，到下一間加油站15，花10單位的燃料，沒有超過燃料箱的油量(10)，則當前油量變成0、備用的加油站多了[10]的油量
2. 目前距離15，到下一間加油站11，花4單位的燃料，超過燃料箱的油量(0)，則拿備用油[10]倒進來，滿足這段行使距離。當前油量變成6、備用的加油站是[5]的油量 
3. 目前距離11，到下一間加油站5，花6單位的燃料，沒有超過燃料箱的油量(6)，則當前油量變成0、備用的加油站多了[2]的油量
4. 目前距離5，到下一間加油站4，花1單位的燃料，超過燃料箱的油量(0)，則拿備用油[5]倒進來，滿足這段行駛距離。當前油量變成4、備用的加油站是[4]的油量
5. 目前距離4，到終點城鎮0，花4單位的燃料，沒有超過燃料箱的油量(4)，則當前油量變成0。
6. 需加2次油才可抵達城鎮

　　題目測資會有些陷阱，比如加油站的位置不一定由小到大，需要自己排序。或者加油站的補給量有可能是0.......很好玩的測資。

　　實作也把城鎮當作最後一家加油站，這樣距離/扣油量的計算才會完整。

難度為Medium

程式碼：

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

struct Stop{
	int dist, amount;
};

bool cmp(const Stop &a, const Stop &b)
{
    return a.dist < b.dist;
}

int main() {
	int n;
	Stop stops[10005];
	int L, curAmount;
	while(cin >> n){
		int ans = 0;
		bool notToTown = false;
		priority_queue<int, vector<int>, less<int> > q;
		for(int i = 0 ; i < n;++i){
			cin >> stops[i].dist >> stops[i].amount;
		}

		cin >> L >> curAmount;
		
		
		stops[n].dist = 0;
		stops[n].amount = 0;
		
		sort(stops, stops + (n+1), cmp);
		
		int curLength = L;
		
		for(int i = n ; i >= 0;--i){
			int curDistance = curLength - stops[i].dist;
			
			while(curAmount - curDistance < 0){
				if(q.empty()){
					notToTown = true;
					break;
				}else{
					curAmount += q.top();
					q.pop();
					ans++;
				}
			}
			
			curAmount -= curDistance;
			q.push(stops[i].amount);
			curLength = stops[i].dist;
		}
		
		if(notToTown){
			cout << "-1" << endl;
		}
		else{
			cout << ans << endl;
		}
	}
	return 0;
}

GITHUB位置：

https://github.com/u8989332/ProblemSolving/blob/master/PKUOnlineJudge/2400-2499/2431.cpp